Segment Trees are Binary Tree which is used to store intervals or segments. That is each node in a segment tree basically stores the segment of an array. Segment Trees are generally used in problems where we need to solve queries on a range of elements in arrays.

Let us consider the following problem to understand Segment Trees.

Problem: We have an array arr[0 . . . n-1]. We should be able to perform the below operations on the array:

1. Find the sum of elements from index l to r where 0 <= l <= r <= n-1.
2. Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

General Solution: A simple solution is to run a loop from index l to r and calculate the sum of elements in the given range. To update a value, simply do arr[i] = x. The first operation takes O(N) time for every query, where N is the number of elements in the range [l,r] and the second operation takes O(1) time.

Can we optimize the time complexity of the first operation in the above solution?

Yes, we can optimize the first operation to be solved in O(1) time complexity by storing presum. We can keep an auxiliary array say sum[] in which the i-th element will store the sum of first i elements of the original array. So, whenever we need to find the sum of a range of elements, we can simply calculate it by (sum[r]-sum[l-1]). But in this solution the complexity to perform the second operation of updating an element increases from O(1) to O(N).

What if the number of query and updates are equal? Can we perform both the operations in O(log n) time once given the array?

We can use a segment tree to perform both of the operations in O(log N) time complexity.

Representation of Segment trees:

1. Leaf Nodes are the elements of the input array.
2. Each internal node represents some merging of the leaf nodes. The merging may be different for different problems. For this problem, merging is the sum of leaves under a node.

An array representation of the tree is used to represent Segment Trees. For each node at index i, the left child is at index 2*i + 1, right child at 2*i + 2 and the parent is at (i - 1)/2.



Array representation of Segment Trees: Like Heap, segment tree is also represented as an array. The difference here is, it is not a complete binary tree. It is rather a full binary tree (every node has 0 or 2 children) and all levels are filled except possibly the last level. Unlike Heap, the last level may have gaps between nodes. Below are the values in the segment tree array for the above diagram.

Array representation of segment tree for input array {1, 3, 5, 7, 9, 11} is,

st[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}

The dummy values are never accessed and have no use. This is some wastage of space due to simple array representation. We may optimize this wastage using some clever implementations, but the code for sum and update becomes more complex.

Construction of Segment Tree from the given array: We start with a segment arr[0 . . . n-1] and every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node.

All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2*n – 1. Note that this does not include dummy nodes.

What is the total size of the array representing segment tree? If n is a power of 2, then there are no dummy nodes. So the size of the segment tree is 2n-1 (n leaf nodes and n-1) internal nodes. If n is not a power of 2, the size of the tree will be 2*x – 1 where x is the smallest of 2 greater than n. For example, when n = 10, then size of array representing segment tree is 2*16-1 = 31.

Query for Sum of given range

Following is the algorithm to get the sum of elements.

int getSum(node, l, r) 
{
   if the range of the node is within l and r
        return value in the node
   else if the range of the node is completely outside l and r
        return 0
   else
        return getSum(node's left child, l, r) + 
               getSum(node's right child, l, r)
}

Updating a value

Like tree construction and query operations, the update can also be done recursively. We are given an index which needs to be updated. Let diff be the value to be added. We start from the root of the segment tree and add diff to all nodes which have given index in their range. If a node doesn’t have given index in its range, we don’t make any changes to that node.

Implementation:

Time Complexity: The time Complexity for tree construction is O(n). There are total 2n-1 nodes, and the value of every node is calculated only once in tree construction.

Time complexity to query is O(Logn). To query a sum, we process at most four nodes at every level and number of levels is O(Logn).

The time complexity of the update is also O(Logn). To update a leaf value, we process one node at every level and number of levels is O(Logn).

The Range Minimum Query is another popular problem which can be solved using Segment Trees. The problems state that, given an array and a list of queries containing ranges, the task is to find the minimum element in the range for every query.

Note: This problem does not require us to perform any update operation on the array.

Representation of Segment trees:

1. Leaf Nodes are the elements of the input array.
2. Each internal node represents a minimum of all leaves under it.

An array representation of the tree is used to represent Segment Trees. For each node at index i, the left child is at index 2*i + 1, the right child at 2*i + 2 and the parent is at (i-1)/2.



We start with a segment arr[0 . . . n-1] and every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the minimum value in a segment tree node.

All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2*n – 1.

Height of the segment tree will be log₂N. Since the tree is represented using array and relation between parent and child indexes must be maintained, the size of memory allocated for segment tree will be 2*2^log₂N - 1.

Query for the minimum value in a given range:
Following is the algorithm to get the minimum element in Range.

// qs --> query start index, qe --> query end index
int RMQ(node, qs, qe) 
{
   if the range of node is within qs and qe
        return value in the node
   else if the range of node is completely outside qs and qe
        return INFINITE
   else
        return min( RMQ(node's left child, qs, qe), 
                    RMQ(node's right child, qs, qe) )
}

Implementation:


Time Complexity: The time complexity for tree construction is O(n). There are total 2n-1 nodes, and the value of every node is calculated only once in tree construction.

Time complexity to query is O(Logn). To query a range minimum, we process at most two nodes at every level and number of levels is O(Logn).